package hot_100;

/**
 * @author: Darven
 * @createTime: 2025-09-28  01:00
 * @description: TODO
 */
public class P74 {
    //    public boolean searchMatrix(int[][] matrix, int target) {
//        for (int i = 0; i < matrix.length; i++) {
//            int mid = binarySearch(matrix[i], target);
//            if(mid!=-1){
//                return true;
//            }
//        }
//
//        return false;
//    }
//
//    private int binarySearch(int[] matrix, int target) {
//        int l = 0;
//        int r = matrix.length - 1;
//        while (l <= r) {
//            int mid = (l + r) >> 1;
//
//            if (matrix[mid] == target) {
//                return mid;
//            } else if (matrix[mid] > target) {
//                r = mid + 1;
//            } else {
//                l = mid - 1;
//            }
//        }
//
//        return -1;
//    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int i = 0;
        int j = matrix[i].length - 1;

        while (i < n && j >= 0) {
            if(matrix[i][j]==target){
                return true;
            }

            if(matrix[i][j]>target){
                j--;
            }else{
                i++;
            }
        }

        return false;
    }

}
